package leetcode.treap;

import lombok.Data;
import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author ：zsy
 * @date ：Created 2021/11/13 23:30
 * @description：树堆 基本操作时间复杂度O(logn)
 * 相对于其他的平衡二叉搜索树，Treap的特点是实现简单，且能基本实现随机平衡的结构。
 */
public class Treap {

    TreapNode root;

    public Treap(TreapNode root) {
        this.root = root;
    }

    public void insert_val(TreapNode node) {
        if (node.priority == 0) {
            node.priority = (int) (Math.random() * 20);
        }
        insert_val(this.root, node);
    }

    private void insert_val(TreapNode root, TreapNode node) {
        if (root == null) {
            root = node;
        } else {
            if (root.val == node.val) return;
            if (root.val > node.val) {
                if (root.left == null) {
                    root.left = node;
                } else {
                    insert_val(root.left, node);
                }
                //判断最小堆
                if (root.priority > node.priority) {
                    right_rotate(root);
                }
            } else {
                if (root.right == null) {
                    root.right = node;
                } else {
                    insert_val(root.right, node);
                }
                //判断最小堆
                if (root.priority > node.priority) {
                    left_rotate(root);
                }
            }
        }
    }

    public void del_val(int val) {
        del_val(root, val);
    }

    private void del_val(TreapNode root, int val) {
        if (root == null) return;
        if (root.val > val) del_val(root.right, val);
        if (root.val < val) del_val(root.left, val);
        else {
            TreapNode node = root;
            while (node.left != null && node.right != null) {
                if (node.left.priority < node.right.priority) {
                    right_rotate(node);
                    node = node.right;
                } else {
                    left_rotate(node);
                    node = node.left;
                }
            }
            if (node.left != null) {
                node.val = node.left.val;
                node.priority = node.left.priority;
                node.left = null;
            } else if (node.right != null) {
                node.val = node.right.val;
                node.priority = node.right.priority;
                node.right = null;
            }
        }
    }

    public boolean contains(TreapNode root, TreapNode node) {
        if (root == null) return false;
        if (root.val == node.val) return true;
        if (root.val > node.val) return contains(root.right, node);
        else
            return contains(root.left, node);
    }

    /**
     * 左旋
     *
     * @param node
     */
    public void left_rotate(TreapNode node) {
        TreapNode temp = new TreapNode(node.val, node.priority);
        temp.right = node.right.left;
        temp.left = node.left;
        node.left = temp;
        node.val = node.right.val;
        node.priority = node.right.priority;
        node.right = node.right.right;
    }

    /**
     * 右旋
     *
     * @param node
     */
    public void right_rotate(TreapNode node) {
        TreapNode temp = new TreapNode(node.val, node.priority);
        temp.left = node.left.right;
        temp.right = node.right;
        node.right = temp;
        node.val = node.left.val;
        node.priority = node.left.priority;
        node.left = node.left.left;
    }

    /**
     * 中序遍历
     * @param node
     */
    public void infixOrder(TreapNode node) {
        if (node == null) return;
        infixOrder(node.left);
        System.out.println(node);
        infixOrder(node.right);
    }

    /**
     *
     */
    public void queue_order() {
        if (root == null) return;
        Queue<TreapNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreapNode cur = queue.poll();
                System.out.print(cur + " ");
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
            }
            System.out.println();
        }
    }


}

@Data
class TreapNode {

    int val;
    int priority;
    TreapNode left;
    TreapNode right;

    public TreapNode(int val) {
        this.val = val;
    }

    public TreapNode(int val, int priority) {
        this.val = val;
        this.priority = priority;
    }

    @Override
    public String toString() {
        return "TreapNode{" +
                "val=" + val +
                ", priority=" + priority +
                '}';
    }
}
